package com.pashanhoo.datastructure.leetcode;

/**
 * @author 胡庆安
 * @version V1.0
 * @Package com.pashanhoo.datastructure.leetcode
 * @date 2020/10/27 13:13
 * @Copyright © 2010-2020 爬山虎科技（扬州）股份有限公司
 */
//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//输入：1->2->4, 1->3->4
//输出：1->1->2->3->4->4
public class Test21 {
    public static void main(String[] args) {
        /*ListNode listNode3 = new ListNode(4);
        ListNode listNode2 = new ListNode(3);
        ListNode listNode1 = new ListNode(1);
        listNode2.next = listNode3;
        listNode1.next = listNode2;

        ListNode listNode6 = new ListNode(4);
        ListNode listNode5 = new ListNode(3);
        ListNode listNode4 = new ListNode(1);
        listNode5.next = listNode6;
        listNode4.next = listNode5;

        final ListNode listNode = mergeTwoLists2(listNode1, listNode4);*/

        ListNode listNode = new ListNode();
        ListNode listNode2 = new ListNode(0);
        mergeTwoLists2(listNode, listNode2);
        //System.out.println(listNode);


    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }


    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        ListNode head = new ListNode();
        ListNode temp = head;

        while (l1 != null || l2 != null) {
            if (l1.val < l2.val) {
                temp.next = new ListNode(l1.val);
                temp = temp.next;
                l1 = l1.next;
            } else if (l1.val == l2.val) {
                temp.next = new ListNode(l1.val);
                temp = temp.next;
                temp.next = new ListNode(l1.val);
                temp = temp.next;
                l1 = l1.next;
                l2 = l2.next;
            } else if (l1.val > l2.val) {
                temp.next = new ListNode(l2.val);
                temp = temp.next;
                l2 = l2.next;
            }

        }
        return head == null?null:head.next;
    }

}
